/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.algorithm
 * author:David
 * Date:2015年8月16日上午11:00:53
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.algorithm;

/**
 * 利用字符串和十进制进位特性实现大数据之间的算术运算
 * @author David
 * @since 2015年8月16日 上午11:00:53
 * @version 
 * @since JDK 1.6
 */
public class BigInt{
	private String valStr;
	private int[] val;
	private String sign;
	/**
	 * @param string
	 */
	public BigInt(String val) {
		this.val=str2IntArr(val);
		this.valStr=val;
	}

	public String add(String val){
		int[]res=null;
		res=add(this.val, str2IntArr(val));
		return toString(res);
	}
	
	public BigInt subtract(BigInt val){
		int[] val2 = str2IntArr(val.getValStr());
		int[] val3 = null;
		int distance = this.val.length-val2.length;
		if(distance>0){
			val3 = new int[this.val.length];
			for(int i=0;i<val2.length;i++){
				val3[distance+i]=val2[i];
			}
			return subtract(this.val, val3);
		}else if(distance<0){
			sign = "-";
			val3 = new int[val2.length];
			for(int i=0;i<this.val.length;i++){
				val3[i-distance]=this.val[i];
			}
			return subtract(val2, val3);
		}
		if(beforeSubtract(this.val, val2)>0){
			return subtract(this.val, val2);
		}else if(beforeSubtract(this.val, val2)<0){
			sign = "-";
			return subtract(val2, this.val);
		}
		return subtract(this.val, val2);
	}
	
	private int beforeSubtract(int[] val1, int[] val2){
		for(int i=0;i<val1.length;i++){
			if(val1[i]==val2[i]){
				val1[i]=val2[i]=0;
			}else if(val1[i]>val2[i]){
				return 1;
			}else{
				return -1;
			}
		}
		return 0;
	}
	
	private BigInt subtract(int[] val1, int[] val2) {
		int[] res = new int[val1.length];
		boolean flag = false;
		for(int i=val1.length-1;i>=0;i--){
			if(flag){
				if(val1[i]==0){
					val1[i] = 9;
				}else{
					val1[i] = val1[i] - 1;
				}
			}
			if(val1[i]<val2[i]){
				res[i] = val1[i]+10-val2[i];
				flag = true;
			}else{
				res[i] =  val1[i]-val2[i];
				flag = false;
			}
		}
		
		int len = res.length;
		for(int i=0;i<res.length;i++){
			if(res[i]!=0){
				break;
			}else{
				len--;
			}
		}
		int[] res2 = new int[len];
		for(int i=res2.length-1;i>=0;i--){
			res2[i]=res[res.length-len+i];
		}
		this.val = res2;
		this.valStr = toString(res2);
		return this;
	}

	public BigInt multiply(){
		
		
		return null;
	}
	
	public BigInt divide(){
		
		
		return null;
	}
	
	
	public BigInt add(BigInt val){
		int[]res=null;
		res=add(this.val, str2IntArr(val.getValStr()));
		return new BigInt(toString(res));
	}
	
	private String toString(int[] arr){
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<arr.length;i++){
			sb.append(arr[i]);
		}
		return sb.toString();
	}
	

	/**
	 * 字符串数字转换int数组
	 * @param val
	 * @return
	 */
	private int[] str2IntArr(String val) {
		char[]ch=val.toCharArray();
		int[]toIntArr=new int[ch.length];
		for(int i=0;i<ch.length;i++){
			toIntArr[i]=Integer.parseInt(ch[i]+"");
		}
		return toIntArr;
	}
	
	/* 加法 */
	public int[] add(int[] a, int[] b) {
		/* 定义进位值，初始为0 */
		int remainder = 0;
		/* 定义返回的数组 */
		int[] res = null;
		int[] c=null;
		if(a.length!=b.length){
			if(a.length<b.length){//a<b
				res=new int[b.length];
				c=new int[b.length];
				for(int i=c.length-a.length,j=0;i<c.length;i++,j++){
					c[i]=a[j];
				}
				add(c, b, remainder, res);
				return res;
			}else{//a>b
				res=new int[a.length];
				c=new int[a.length];
				for(int i=c.length-b.length,j=0;i<c.length;i++,j++){
					c[i]=b[j];
				}
				add(c, a, remainder, res);
				return res;
			}
			
		}else{
			res=new int[a.length];
			add(a, b, remainder, res);
			return res;
		}
	}

	//对2个位数相同的数进行加法运算
	private void add(int[] a, int[] b, int remainder, int[] res) {
		for (int i = a.length - 1; i >= 0; i--) {
			res[i] = a[i] + b[i] + remainder;
			if (res[i] < 10) {
				remainder = 0;
			} else {
				remainder = 1;
				if(i!=0)
					res[i] = res[i]-10;
			}
		}
	}

	
	@Override
	public String toString() {
		if(sign!=null){
			return sign+this.valStr;
		}
		return this.valStr;
	}

	public String getValStr() {
		return valStr;
	}

	public String getSign() {
		return sign;
	}

	public void setSign(String sign) {
		this.sign = sign;
	}
	
	
}
